<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        插入排序思路：
        - 从第二个数开始往前比
        - 比它大就往后排
        - 以此类推进行到最后一个数

        时间复杂度也是 O(n*n) 但是在排序小型数组时，插入排序比选择和冒泡要好
     -->
</head>
<body>
    <!-- 
        将第一个元素标记为已排序
        遍历每个没有排序过的元素
        提取元素 x
        i = 最后排序过元素的指数 到 0的遍历
        如果现在排序过的数元素 > 提取的元素
            将排序过的元素后移一位
        否则，插入提取的元素
     -->
    <script>
        Array.prototype.insertionSort = function() {
            for (let i = 1; i < this.length; i++) {
                const temp = this[i];
                let j = i;
                while (j>0) {
                    if (this[j - 1] > temp) {
                        this[j] = this[j-1];
                    } else {
                        break;
                    }
                    j--;
                }
                this[j] = temp;
            }
        };

        const arr = [2, 4, 5, 3, 1];
        arr.insertionSort();
        console.log(arr);
    </script>
</body>
</html>